package org.example.basic_sort;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 归并排序
 * 先把数组分为2个部分，是他们分别有序 再合并到一起
 *
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 * 稳定性：稳定
 */
public class Code04_mergeSort {
    public int min = 0;
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        process(arr,0, arr.length - 1);
    }

    public static void process(int[] arr,int L, int R) {
        if( L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr,L,mid);
        process(arr,mid + 1,R);
        merge(arr,L,mid,R);

    }
    public static void merge(int[] arr,int L, int M ,int R) {
        int[] help = new int[R - L + 1];
        int i =0;
        int p1 = L;
        int p2 = M + 1;
        while(p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for(i = 0;i < help.length; i++){
            arr[L + i] = help[i];
        }
    }

    public static void main(String[] args) {
//        int[] arr = {1,3,4,2,5};
//        mergeSort(arr);
//        for (int i : arr) {
//            System.out.println(i);
//        }

        Set<List<Integer>> objects = new HashSet<>();
        objects.add(List.of(1,2,3));
        objects.add(List.of(13,2));
        System.out.println(objects);
    }
}
